package oct2013.linkednode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversalII {
	public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		if (root != null) {
			q.add(root);
		}
		TreeNode cur;
		int level1 = 1, level2 = 0;
		ArrayList<Integer> curLevel = new ArrayList<Integer>();
		while (!q.isEmpty()) {
			cur = q.poll();
			level1--;
			if (cur != null) {
				curLevel.add(cur.val);
				q.add(cur.left);
				q.add(cur.right);
				level2 += 2;
			}
			if (level1 == 0) {
				level1 = level2;
				level2 = 0;
				if (curLevel.size() > 0) {
					res.add(curLevel);
					curLevel = new ArrayList<Integer>();
				}
			}
		}
		return res;
	}
}
